home *** CD-ROM | disk | FTP | other *** search
-
-
- IEN 173
-
-
- Time Synchronization in DCNET Hosts
- D.L. Mills, COMSAT Laboratories
- 25-Feb-81
-
-
- Introduction
-
- The difficulty in establishing an absolute time reference
- for use in internet measurements and experiments has been
- often lamented. While time standards calibrated to the
- precision necessary for internet delay measurements (in the
- order of a millisecond) are readily available, the cost to
- equip each host which may participate in these experiments
- is significant and the broadcast services they depend upon
- may not be available where needed. This note describes an
- alternative mechanism using local-net protocols to
- synchronize a logical clock in each of a set of internet
- hosts to a single physical clock, such as an NBS radio
- clock. The mechanism has been incorporated as an integral
- component of the DCNET network routing algorithm and depends
- for its accuracy upon the careful control of link delays.
- For this reason it may not be practically applicable as a
- retrofit in the ARPANET, for example. Nevertheless, the
- principles can be applied in cases where somewhat less
- precision is acceptable and where the participating hosts or
- gateways support the required protocol.
-
- The DCNET Routing Algorithm
-
- The DCNET includes a number of PDP11-compatible hosts
- interconnected by dedicated and dial-up links of various
- types, including simple synchronous and asynchronous
- point-to-point links, high-speed interprocessor channels and
- self-contained retransmission systems. All of these links
- include inherent delays which vary with transmission rate,
- message length and coding, as well as occasional
- retransmissions. In addition, the host operating system can
- introduce delays due to interrupt latency, interprocess
- communication and process scheduling. These delays
- typically include a fixed component due to propagation
- phenomena, together with a relatively small variable
- component due to internal queueing, coding and
- retransmission mechanisms.
-
- The DCNET architectural design includes the notion of
- virtual host, which is a process resident in a physical host
- and labelled with a unique internet address. One or more of
- these virtual hosts can reside in a single physical host and
- can migrate about the network from time to time in arbitrary
- ways. Each virtual host can support multiple internet
- protocols, connections and, in addition, a virtual clock.
- Each physical host contains a physical clock which can
- operate at an arbitrary rate and, in addition, a 32-bit
-
- Time Synchronization in DCNET Hosts PAGE 2
-
-
-
- logical clock which operates at 1000 Hz. Not all physical
- hosts implement the full 32-bit precision; however, in such
- cases the resolution of the logical clock may be somewhat
- less.
-
- Routing of datagrams from a physical host to each of the
- virtual hosts in the network is determined by a set of Host
- Tables, one in each physical host, which are updated by
- HELLO messages exhanged on the links connecting them. The
- HELLO messages are exchanged frequently, but not so as to
- materially degrade the throughput of the link for ordinary
- data messages. They contain information necessary to
- compute the roundtrip delay and logical clock offset of the
- receiving physical host relative to the sending one,
- together with a table of delay and offset estimates computed
- between the sending physical host and each of the virtual
- hosts in the network. For the purpose of these estimates
- the delay and offset of each virtual host relative to the
- physical host in which it resides is assumed zero.
-
- The Host Table is updated by HELLO messages from each
- neighboring physical host and in certain other cases. The
- updating algorithm is similar to that used in the ARPANET
- and other places in that the roundtrip delay calculated to a
- neighbor is added to each of the delay estimates given in
- its HELLO message and compared with the corresponding delay
- estimates in the Host Table. If a delay computed in this
- way is less than the delay already in the Host Table, the
- routing to the corresponding virtual host is changed
- accordingly. The detailed operation of this algorithm,
- which includes provisions for host up-down logic and loop
- suppression, is summarized elsewhere [1].
-
- Virtual Clocks
-
- The Host Table update procedure represents a convenient
- mechanism to implement a common time reference for each
- logical clock in the network. For this purpose each virtual
- clock residing in a physical host is assumed to run in
- synchronism with zero offset relative to the logical clock
- of that host. The offsets of the other virtual hosts in the
- network, relative to this logical clock, are computed along
- with the delays as HELLO messages arrive from neighboring
- physical hosts. A physical host, upon receiving a HELLO
- message, adds one-half the difference between its logical
- clock and its neighbor's logical clock contained in the
- HELLO message to each of the offset values in the message
- and stores the result in its own Host Table. Note that both
- the delay and offset values are stored only if the neighbor
- is in fact on the least-delay path to the virtual host and
- that the link delay is assumed equal in both directions.
- Also, note that should a virtual host move from one physical
- host to another, the delays and offsets in all Host Tables
-
- Time Synchronization in DCNET Hosts PAGE 3
-
-
-
- relative to that virtual host would likely change.
-
- Any user process in a physical host can reference its
- time-of-day calculations to any virtual host in the network
- by simply adding the appropriate virtual clock offset to the
- current value of the logical clock. Ordinarily, all network
- experiments use the same virtual host for this purpose,
- although not necessarily the same one in successive
- experiments. In the current implementation one of the
- physical hosts contains a special virtual host connected to
- an NBS radio clock. The offset stored in the Host Table
- corresponding to this virtual host reflects the offset of
- this clock relative to the logical clock. Using the above
- mechanism, the remaining physical hosts can reference their
- logical clocks to the receiver as well. One of the physical
- hosts is shortly to be moved not far from an atomic clock
- which is referenced to the Naval Observatory clock using a
- local television station. We are now assembling interface
- hardware for access to this standard and plan to use the
- above mechanism to reference all clocks to it.
-
- Implementation Considerations
-
- The absolute accuracy of the available NBS radio clocks is
- claimed to be of the order of a millisecond. Since this
- precision compares with that of the standard internet
- timestamps used for the most precise delay measurements, it
- would be natural to strive for a corresponding precision
- within a set of hosts using the mechanism described above.
- Ordinarily, this would require a crystal oscillator, counter
- and interface at each host. The oscillator stability found
- in commercial equipment of this type is of the order of a
- few parts per million under laboratory conditions. An
- uncorrected logical clock based on this equipment could be
- expected to maintain time to within a millisecond for at
- least eight minutes and to within three minutes in a year.
-
- In the case of the mechanism described above, the
- corrections take the form of offsets contained in periodic
- HELLO messages. A careful analysis of the non-systematic
- errors inherent in these messages reveals contributions from
- a number of sources dominated by the following:
-
- 1. The interval between the instant the local clock is read
- and the departure of the first bit of the timestamp on
- the link.
-
- 2. The effect of the data coding conventions (e.g.
- character stuffing or bit stuffing) used to maintain
- data transparency.
-
- 3. The effect of retransmissions, where used.
-
- Time Synchronization in DCNET Hosts PAGE 4
-
-
-
- 4. The interval between the arrival of the first bit of the
- timestamp and the instant it is compared with the local
- clock.
-
- The effects of the first and last of these delays has been
- minimized in the DCNET implementation by careful control of
- internal latencies and scheduling mechanisms and is limited
- to the order of a millisecond. The effects of character and
- bit stuffing can be estimated under the assumption that all
- character codes are equally likely. In that case, the
- effects of character stuffing would contribute a factor of
- about 1/256 to the uncertainty in data rate and the effects
- of bit stuffing would contribute about 1/32. Thus, for the
- case of 1200-bps character-stuffing links carrying HELLO
- messages of typically 800 bits, the uncertainty would be of
- the order of two milliseconds. The effects of bit stuffing
- in the high-speed links are negligible in comparison.
- Although HELLO messages are never retransmitted by a DCNET
- host, some of the DCNET links, in particular those based on
- the ACC Error Control Units (ECU), contain internal
- retransmission features. Since retransmissions occur so
- seldom in the present configuration, their effects have been
- ignored; however, a simple range-gate technique similar to
- that used in radar systems could be used to filter out
- retransmissions, should that become a problem.
-
- From the above considerations the uncertainty in delays
- measured using HELLO messages can be conservatively assumed
- in the order of five milliseconds. For ease of analysis in
- the following, we will assume the uncertainty to be a random
- variable with a zero-mean Gaussian distribution and a
- standard deviation of five milliseconds. Thus, in order to
- reduce the uncertainty to the order of a millisecond,
- something over 25 independent samples would be required.
- The maximum interval between successive HELLO messages is
- thirty seconds, so that the required precision can in
- principle be achieved in about twelve minutes.
-
- Precise determination of clock offsets requires that the
- drift rates between the various logical clocks be estimable
- with sufficient precision. The approach chosen in the DCNET
- design has been to initialize a variable representing the
- current offset of the local logical clock relative to that
- of a neighbor each time a HELLO message arrives from that
- neighbor which updates the Host Table entry for the selected
- virtual host. Once each second the period of the logical
- clock is increased by a quantity equal to 1/1024 of this
- variable and the variable is decreased by the same quantity.
- The effect is that of a first-order recursive filter in
- smoothing the corrections and distributing them so as to
- minimize the phase jitter as viewed by the user process. In
- addition, if updates from the selected virtual host are lost
- due to failure of some host or link, the logical clock will
-
- Time Synchronization in DCNET Hosts PAGE 5
-
-
-
- continue the correction process until the last offset
- received is compensated.
-
- In order to provide for the initial setting of the logical
- clock and subsequent drift correction without disruptive
- phase discontinuties, the full 32-bit clock value is stored
- only if the (signed) offset exceeds 16 bits; that is, only
- if the high-order 16 bits must be changed. In other cases
- the low-order 16 bits are corrected by slewing the phase of
- the clock according to the current offset as described
- above. The high-order 16 bits correspond roughly to
- minutes, while the low-order 16 bits correspond to
- milliseconds. Most internet measurments will be concerned
- primarily with the latter, so this behavior is appropriate.
- This yields a slew rate of about one microsecond per second
- for each millisecond of offset.
-
- The dynamics of this procedure insure a smooth transition in
- apparent drift rate from a maximum of 30 parts per thousand
- for the maximum offset to one part per million for the
- smallest. The maximum time required to slew the phase of a
- physical clock over the full (plus-minus) thirty-second
- range to steady state is about two hours. During the
- slewing interval the offset estimates continue to be valid,
- although of somewhat degraded accuracy.
-
- In a multiple-host network where the logical-clock
- corrections must pass through a number of physical hosts,
- the robustness of this method depends on the cooperation of
- all intervening hosts. In general, this requires all hosts
- to track the same virtual host offset and, in addition,
- introduces additional dynamics in the drift-correction
- process. The effect is that of a set of coupled first-order
- recursive filters, where the input of each stage is
- connected to the output of the previous stage, and all have
- the same time constant described previously. So long as the
- drift rates are constant over at least several hours, this
- is not a problem; however, in the case where some logical
- clocks are derived from power-line sources, this can lead to
- significant loss in accuracy.
-
- On Power Line Clocks
-
- The short-term drift rates of power-line clocks relative to
- standard time have been observed to exceed several parts per
- thousand, with sharp changes in sign and magnitude occuring
- near periods of large load fluctuations. In experiments
- with the current DCNET implementation, discrepancies of
- several seconds are routinely observed between the
- power-line clock and the NBS radio clock. However, it is
- evident that the power systems for considerable portions of
- this country are closely synchronized in phase relative to
- each other. For instance, the DCNET hosts at COMSAT
-
- Time Synchronization in DCNET Hosts PAGE 6
-
-
-
- Headquarters in Washington, D.C., and at Ford Scientific
- Research Laboratories in Dearborn, Michigan, have never been
- observed to slip a power-line cycle relative to each other.
-
- These observations suggest that, if logical clocks are to be
- synchronized to an atomic clock or NBS radio clock, then
- physical clocks based on the power mains are not feasible,
- at least for accuracies of the order of milliseconds. On
- the other hand, for the short-term delay measurements
- required for many internet experiments and where reference
- to absolute time is not essential, the use of the power
- mains as a synchronization reference may be quite practical.
- This holds, of course, only in those cases where the power
- systems in the areas where measurements are made are in fact
- synchronous and probably would not apply, for example, for
- European sites.
-
- On Radio Clocks
-
- Two of the NBS radio clocks on the market include the
- Spectracom 8170 WWVB Synchronized Clock and the True Time
- 468-DC Satellite Synchronized Clock. The former uses the
- 60-KHz NBS broadcast from Boulder, Colorado, while the
- latter uses the NOAA GOES satellites. Both have claimed
- accuracy in the order of a millisecond and both support a
- service area including the continental US. A Spectracom
- 8170 is now in service connected to one of the DCNET hosts
- and serves as a master clock for the network. A few notes
- on its characteristics may be of interest, especially to
- others in the internet community planning on using similar
- equipment.
-
- The characteristics of electromagnetic wave propagation at
- 60 KHz combine some features of the waveguide model
- applicable at frequencies below about 30 KHz and the ray
- model applicable at higher frequencies [2]. Both models
- explain how the E layer, an ionized region about 100 km
- above the earth's surface, guides or reflects
- electromagnetic waves over long distances. In the case of
- 60-KHz transmissions from Boulder, the models predict
- greater signal attenuation at times of the most intense
- ionizing radiation from the sun on the D region, which lies
- just below the E region and through which the signals must
- pass. Thus, one would expect that received signal levels
- would be highest at nighttime in winter and lowest in
- daytime in summer, with respect to the midpoint of the path
- from Boulder to the receiver. This has been observed in
- Washington, DC, where the receiver often drops out of phase
- lock for varying periods in the late afternoon.
- Measurements of the received signal level with a
- communications reveiver confirm variations of 20-30
- decibels.
-
- Time Synchronization in DCNET Hosts PAGE 7
-
-
-
- Atmospheric discharges (called sferics) due to lightning can
- be a severe problem at these frequencies in Summer and could
- be expected to disrupt the receiver during summer evenings
- when propagation conditions are relatively good from active
- electrical areas like the Gulf Coast. Although other
- stations share the 60-KHz assigned frequency, including MSF
- in Rugby, UK, co-channel interference does not seem to be a
- problem. On the other hand, some household electrical
- appliances, including television deflection circuits and
- solid-state lamp dimmers, can generate copious harmonics
- that disrupt the receiver. The ferrite antenna supplied
- with the receiver does not seem to be as effective as would
- ordinarily be expected in dealing with this problem.
-
- Even when phase lock has been lost, the receiver coasts
- indefinately using the last clock update received. Although
- the receiver indicates a signal loss of over ten minutes,
- both by a front-panel indicator and in the time message sent
- to the attached host, the indicated time should remain
- accurate to within an order of one part in a million, as
- suggested by tests using an accurate frequency counter. The
- DCNET implementation polls the receiver every thirty seconds
- and tracks the time messages as long as they are available,
- but retains the last received message for later inspection,
- if desired. In addition, if the time messages are lost the
- system continues to follow the information in the last
- message.
-
- Summary and Conclusions
-
- The above analysis indicates that logical clocks in
- neighboring physical hosts can be synchronized using
- ordinary local-network routing update messages, so long as
- the oscillator drift rates are stable and do not differ
- radically. A multiple-host network can readily be
- synchronized so long as each pair of neighboring hosts can,
- although this can require rather long settling times. Here,
- two hosts are assumed synchronized when the offsets between
- their respective logical clocks can be calculated to a
- precision of the order of a millisecond.
-
- Delay and offset variances along internet paths are likely
- to be so large as to make the technique described above
- impractical, at least if millisecond accuracy is to be
- preserved. The present plan of installing radio clocks in
- the internet gateways appears to be the most sensible
- alternative. The gateways thus form an attractive time
- reference for the hosts on the attached local networks. The
- gateways themselves could include the offsets between their
- own clocks in Gateway-Gateway Protocol (GGP) routing update
- messages, if not all of them were equipped with NBS radio
- clocks, and could conveniently provide this information in
- GGP echo messages to the local network hosts. In order for
-
- Time Synchronization in DCNET Hosts PAGE 8
-
-
-
- this to be most effective, the timestamping mechanism used
- by the gateways (and hosts, of course) should be implemented
- as close to the network interface driver as possible,
- preferably by the driver itself.
-
- A local-network host can synchronize its logical clock to a
- gateway by a mechanism suggested by the DCNET routing update
- procedure. The host sends a GGP echo packet timestamped
- with its logical clock to a gateway. The gateway timestamps
- it with its own logical clock upon arrival and again when it
- is retransmitted to the host. The local host uses these
- three timestamps, together with the time of arrival of the
- reply packet, to compute the delay and offset as described
- above. The use of three timestamps in the GGP echo packet
- allows the host to compensate for the internal delay within
- the gateway, if significant.
-
- References
-
- 1. COMSAT Laboratories Quarterly Progress Reports. Stay
- tuned.
-
- 2. Davies, K. Ionospheric Radio Propagation. NBS
- Monograph 80, National Bureau of Standards, Washington,
- DC, 1966.
-
-
-